class Solution {
public:
    string path;
    vector<string> ret;
    string gener[2] = {"(", ")"};
    vector<string> generateParenthesis(int n) {
        dfs(0, 0, n);
        return ret;
    }
    void dfs(int left, int right, int n) {
        if (right == n) {
            ret.push_back(path);
            return;
        }
        if (left < n) {
            path.push_back('(');
            dfs(left + 1, right, n);
            path.pop_back();
        }
        if (right < left) {
            path.push_back(')');
            dfs(left, right + 1, n);
            path.pop_back();
        }
    }
};